package xin.leetcode;

import java.util.Arrays;
import java.util.List;

/**
 * <pre>
 * 二分查找
 * </pre>
 *
 * @author lixin_ma@outlook.com
 * @since 2021/2/19
 */
public class BinarySearch {
	
	public static void main(String[] args) {
		
		/* ########## test search ########## */
//		int[] nums = {-1, 0, 3, 5, 9, 12};
//		System.out.println(search(nums, 9));
//		System.out.println(search(nums, 2));
//		int[] nums2 = {5};
//		System.out.println(search(nums2, -5));
		
		/* ########## test mySqrt ########## */
//		System.out.println("1 -> " + mySqrt(1));
//		System.out.println("2 -> " + mySqrt(2));
//		System.out.println("4 -> " + mySqrt(4));
//		System.out.println("8 -> " + mySqrt(8));
//		System.out.println("9 -> " + mySqrt(9));
//		System.out.println("16 -> " + mySqrt(16));
//		System.out.println("111 -> " + mySqrt(111));
//		System.out.println("11111 -> " + mySqrt(11111));
		
		
		/* ########## test firstBadVersion ########## */
//		firstBadVersion(5);
		
		/* ########## test findPeakElement ########## */
//		int[] nums = {1,2,1,3,5,6,4};
//		int[] nums = {1,2,3,1};
//		int[] nums = {1};
//		int[] nums = {1, 2, 3, 3, 4, 5};
//		System.out.println(findPeakElement(nums));
		
		/* ########## test findMin ########## */
//		int[] nums = {3, 4, 5, 1, 2};
//		int[] nums = {3, 4, 5, 6, 2};
//		int[] nums = { 4,5,3};
//		int[] nums = {2};
//		System.out.println(findMin(nums));
		
		/* ########## test searchRange ########## */
		int[] nums = null;
		int[] res = null;
//		nums = new int[]{5, 7, 7, 8, 8, 10};
//		res = searchRange(nums, 7);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		res = searchRange(nums, 8);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		res = searchRange(nums, 6);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		nums = new int[]{1,3};
//		res = searchRange(nums, 1);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		nums = null;
//		res = searchRange(nums, 0);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		nums = new int[]{1};
//		res = searchRange(nums, 1);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		nums = new int[]{3,3,3};
//		res = searchRange(nums, 3);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
//		nums = new int[]{1,2,3};
//		res = searchRange(nums, 2);
//		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
//		System.out.println("----------");
		nums = new int[]{5, 7, 7, 7, 8, 10};
		res = searchRange(nums, 7);
		Arrays.stream(res).forEach(item -> System.out.print(item + " "));
		System.out.println("----------");
		
	}
	
	/**
	 * 给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。
	 * 示例 1:
	 * <p>
	 * 输入: nums = [-1,0,3,5,9,12], target = 9
	 * 输出: 4
	 * 解释: 9 出现在 nums 中并且下标为 4
	 * 示例2:
	 * <p>
	 * 输入: nums = [-1,0,3,5,9,12], target = 2
	 * 输出: -1
	 * 解释: 2 不存在 nums 中因此返回 -1
	 * <p>
	 * 提示：
	 * <p>
	 * 你可以假设 nums中的所有元素是不重复的。
	 * n将在[1, 10000]之间。
	 * nums的每个元素都将在[-9999, 9999]之间。
	 */
	public static int search(int[] nums, int target) {
		if (nums == null || nums.length == 0) {
			return -1;
		}
		int result = -1;
		int left = 0;
		int right = nums.length - 1;
		do {
			int mid = left + (right - left) / 2;
			if (target == nums[mid]) {
				result = mid;
				break;
			} else if (target > nums[mid]) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
			
		} while (left <= right);
		return result;
	}
	
	/**
	 * x的平方根
	 * 实现int sqrt(int x)函数。
	 * <p>
	 * 计算并返回x的平方根，其中x 是非负整数。
	 * <p>
	 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
	 * <p>
	 * 示例 1:
	 * <p>
	 * 输入: 4
	 * 输出: 2
	 * <p>
	 * 示例 2:
	 * <p>
	 * 输入: 8
	 * 输出: 2
	 * 说明: 8 的平方根是 2.82842...,
	 * 由于返回类型是整数，小数部分将被舍去。
	 */
	public static int mySqrt(int x) {
		int result = 0;
		if (x == 0) {
			return result;
		}
		int left = 0;
		int right = x;
		do {
			int mid = left + (right - left) / 2;
			if (x == Math.pow(mid, 2)) {
				result = mid;
				break;
			} else if (x == Math.pow(left, 2)) {
				result = left;
				break;
			} else if (x == Math.pow(right, 2)) {
				result = right;
				break;
			} else if (left + 1 == right && Math.pow(left, 2) < x && x < Math.pow(right, 2)) {
				result = left;
				break;
			} else if (x > Math.pow(mid, 2)) {
				left = mid;
			} else {
				right = mid;
			}
			
		} while (left <= right);
		return result;
	}
	
	/**
	 * 猜数字大小
	 * 猜数字游戏的规则如下：
	 * <p>
	 * 每轮游戏，我都会从1到n 随机选择一个数字。 请你猜选出的是哪个数字。
	 * 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
	 * 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1或 0）：
	 * <p>
	 * -1：我选出的数字比你猜的数字小 pick < num
	 * 1：我选出的数字比你猜的数字大 pick > num
	 * 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
	 * 返回我选出的数字。
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：n = 10, pick = 6
	 * 输出：6
	 * 示例 2：
	 * <p>
	 * 输入：n = 1, pick = 1
	 * 输出：1
	 * 示例 3：
	 * <p>
	 * 输入：n = 2, pick = 1
	 * 输出：1
	 * 示例 4：
	 * <p>
	 * 输入：n = 2, pick = 2
	 * 输出：2
	 * <p>
	 * 提示：
	 * <p>
	 * 1 <= n <= 231 - 1
	 * 1 <= pick <= n
	 * <p>
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xee4ev/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public static int guessNumber(int n) {
		int result = -1;
		int left = 1;
		int right = n;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int res = guess(mid);
			if (res == 0) {
				result = mid;
				break;
			} else if (res == 1) {
				left = mid + 1;
			} else if (res == -1) {
				right = mid - 1;
			}
		}
		;
		return result;
	}
	
	/**
	 * 搜索旋转排序数组
	 * 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为[4,5,6,7,0,1,2] ）。
	 * <p>
	 * 请你在数组中搜索target ，如果数组中存在这个目标值，则返回它的索引，否则返回-1。
	 * <p>
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：nums = [4,5,6,7,0,1,2], target = 0
	 * 输出：4
	 * 示例2：
	 * <p>
	 * 输入：nums = [4,5,6,7,0,1,2], target = 3
	 * 输出：-1
	 * 示例 3：
	 * <p>
	 * 输入：nums = [1], target = 0
	 * 输出：-1
	 * <p>
	 * 提示：
	 * <p>
	 * 1 <= nums.length <= 5000
	 * -10^4 <= nums[i] <= 10^4
	 * nums 中的每个值都 独一无二
	 * nums 肯定会在某个点上旋转
	 * -10^4 <= target <= 10^4
	 * <p>
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xeog5j/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public static int search2(int[] nums, int target) {
		int result = -1;
		int left = 0;
		int right = nums.length - 1;
		do {
			int mid = left + (right - left) / 2;
			int res = nums[mid];
			if (res == target) {
				return mid;
			} else if (nums[left] <= res) {
				if (target < res && target >= nums[left])
					right = mid - 1;
				else
					left = mid + 1;
			} else {
				if (target <= nums[right] && target > res)
					left = mid + 1;
				else
					right = mid - 1;
			}
		} while (left <= right);
		return result;
	}
	
	/**
	 * 第一个错误的版本
	 * 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
	 * <p>
	 * 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
	 * <p>
	 * 你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
	 * <p>
	 * 示例:
	 * <p>
	 * 给定 n = 5，并且 version = 4 是第一个错误的版本。
	 * <p>
	 * 调用 isBadVersion(3) -> false
	 * 调用 isBadVersion(5)-> true
	 * 调用 isBadVersion(4)-> true
	 * <p>
	 * 所以，4 是第一个错误的版本。
	 * <p>
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xepthr/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public static int firstBadVersion(int n) {
		int left = 1, right = n;
		while (left < right) {
			int mid = left + (right - left) / 2;
			boolean midVersion = isBadVersion(mid);
			if (isBadVersion(left)) {
				return left;
			} else if (!midVersion) {
				// mid是好版本 则向右移动left
				left = mid + 1;
			} else {
				// mid是坏版本 则向左移动right
				right = mid;
			}
			System.out.println("##");
			System.out.println(" left : " + left);
			System.out.println(" right : " + right);
		}
		if (isBadVersion(left)) {
			return left;
		}
		return -1;
	}
	
	/**
	 * 寻找峰值
	 * <p>
	 * 这道题需要需注意一点是边界起始也算是一种解
	 * <p>
	 * 峰值元素是指其值大于左右相邻值的元素。
	 * <p>
	 * 给你一个输入数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
	 * <p>
	 * 你可以假设nums[-1] = nums[n] = -∞ 。
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：nums = [1,2,3,1]
	 * 输出：2
	 * 解释：3 是峰值元素，你的函数应该返回其索引 2。
	 * 示例2：
	 * <p>
	 * 输入：nums = [1,2,1,3,5,6,4]
	 * 输出：1 或 5
	 * 解释：你的函数可以返回索引 1，其峰值元素为 2；
	 * 或者返回索引 5， 其峰值元素为 6。
	 * <p>
	 * 提示：
	 * <p>
	 * 1 <= nums.length <= 1000
	 * -231 <= nums[i] <= 231 - 1
	 * 对于所有有效的 i 都有 nums[i] != nums[i + 1]
	 * <p>
	 * 进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？
	 * <p>
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xem7js/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public static int findPeakElement(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] < nums[mid + 1]) { // 向左爬坡移动
				left = mid + 1;
			} else {  // 向左爬坡移动
				right = mid;
			}
		}
		return left;
	}
	
	/**
	 * 寻找旋转排序数组中的最小值
	 * <p>
	 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组[0,1,2,4,5,6,7] 可能变为[4,5,6,7,0,1,2] 。
	 * <p>
	 * 请找出其中最小的元素。
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：nums = [3,4,5,1,2]
	 * 输出：1
	 * 示例 2：
	 * <p>
	 * 输入：nums = [4,5,6,7,0,1,2]
	 * 输出：0
	 * 示例 3：
	 * <p>
	 * 输入：nums = [1]
	 * 输出：1
	 * <p>
	 * 提示：
	 * <p>
	 * 1 <= nums.length <= 5000
	 * -5000 <= nums[i] <= 5000
	 * nums 中的所有整数都是 唯一 的
	 * nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转
	 * <p>
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xeawbd/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public static int findMin(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (nums[mid] > nums[right]) {
				left = mid + 1;
			} else if (nums[mid] < nums[right]) {
				right = mid;
			} else {
			
			}
			
		}
		return nums[left];
	}
	
	/**
	 * 在排序数组中查找元素的第一个和最后一个位置
	 * <p>
	 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
	 * <p>
	 * 如果数组中不存在目标值 target，返回[-1, -1]。
	 * <p>
	 * 进阶：
	 * <p>
	 * 你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：nums = [5,7,7,8,8,10], target = 8
	 * 输出：[3,4]
	 * 示例2：
	 * <p>
	 * 输入：nums = [5,7,7,8,8,10], target = 6
	 * 输出：[-1,-1]
	 * 示例 3：
	 * <p>
	 * 输入：nums = [], target = 0
	 * 输出：[-1,-1]
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * 0 <= nums.length <= 105
	 * -109<= nums[i]<= 109
	 * nums是一个非递减数组
	 * -109<= target<= 109
	 * <p>
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xenp13/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public static int[] searchRange(int[] nums, int target) {
		int low = search3(nums, target, true);// 先找 低位
		int high = search3(nums, target, false) - 1; // 再找 高位
		if (low <= high && high < nums.length && nums[low] == target && nums[high] == target) {
			return new int[]{low, high};
		}
		return new int[]{-1, -1};
	}
	
	
	/**
	 * 找到 K 个最接近的元素
	 *
	 * 给定一个排序好的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
	 *
	 * 整数 a 比整数 b 更接近 x 需要满足：
	 *
	 * |a - x| < |b - x| 或者
	 * |a - x| == |b - x| 且 a < b
	 *
	 *
	 * 示例 1：
	 *
	 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
	 * 输出：[1,2,3,4]
	 * 示例 2：
	 *
	 * 输入：arr = [1,2,3,4,5], k = 4, x = -1
	 * 输出：[1,2,3,4]
	 *
	 *
	 * 提示：
	 *
	 * 1 <= k <= arr.length
	 * 1 <= arr.length<= 104
	 * 数组里的每个元素与x 的绝对值不超过 104
	 *
	 * 作者：力扣 (LeetCode)
	 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xeve4m/
	 * 来源：力扣（LeetCode）
	 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
	 */
	public List<Integer> findClosestElements(int[] arr, int k, int x) {
		// 搜索下标
		int index = search(arr,x);
		if(index == -1){
		
		}else{
			int ofLeft = index - k  + 1;
			int left = ofLeft<0?0:ofLeft ;
			int ofRight = index + k  - 1;
			int right = ofRight > arr.length-1 ? arr.length-1 : ofRight ;
		}
		return  null;
	}
	
	public static int search3(int[] nums, int target, boolean lower) {
		int left = 0;
		int right = nums.length - 1;
		int res = nums.length;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (nums[mid] > target || (lower && nums[mid] >= target)) {
				right = mid - 1;
				res = mid;
			} else {
				left = mid + 1;
			}
		}
		return res;
	}
	
	
	static int guess(int num) {
		return 0;
	}
	
	static boolean isBadVersion(int version) {
		return version >= 4;
	}
}
